// BEGIN CUT HERE
// PROBLEM STATEMENT
// Character j in element i (both 0-based) of messages denotes how many messages employee i sent to employee j.  You will return a vector <int> containing the hierarchy of the employees within the company.  Element 0 is the highest ranked employee, and so forth.  The returned ranking should minimize the number of messages sent from lower ranked employees to higher ranked employees.  If multiple solutions are possible, return the one with element 0 minimal.  If there are still ties, minimize element 1, etc.
/*
DEFINITION
Class:CompanyMessages
Method:getRank
Parameters:vector <string>
Returns:vector <int>
Method signature:vector <int> getRank(vector <string> messages)


CONSTRAINTS
-messages will contain between 2 and 15 elements inclusive.
-Each element of messages will contain exactly N characters, where N is the number of elements in messages.
-Each character in messages will be a digit ('0'-'9').
-Character i in element i of messages will be '0'.


EXAMPLES

0)
{"000",
 "000",
 "000"}

Returns: {0, 1, 2 }

Here no messages are sent.

1)
{"000",
 "100",
 "010"}

Returns: {2, 1, 0 }

Person 2 sends a message to person 1 and person 1 sends one to person 0.  The hierarchy is clear.

2)
{
"012105",
"601745",
"830479",
"043086",
"349904",
"649810"}

Returns: {4, 2, 1, 5, 0, 3 }

A lot of messages sent around.*/

#pragma warning(disable:4018)  // signed/unsigned mistatch
#pragma warning(disable:4244)  // w64 to int cast
#pragma warning(disable:4267)  // big to small -- possible loss of data
#pragma warning(disable:4786)  // long identifiers
#pragma warning(disable:4800)  // forcing int to bool
#pragma warning(disable:4996)  // deprecations
// END CUT HERE
#include "assert.h"
#include "ctype.h"
#include "float.h"
#include "math.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "stdarg.h"
#include "time.h"
#include "algorithm"
#include "numeric"
#include "functional"
#include "utility"
#include "bitset"
#include "vector"
#include "list"
#include "set"
#include "map"
#include "queue"
#include "stack"
#include "string"
#include "sstream"
#include "iostream"
using namespace std;

// BEGIN CUT HERE
#define all(v) (v).begin(), (v).end()
typedef long long i64;
template <class T> void make_unique(T& v) {sort(all(v)); v.resize(unique(all(v)) - v.begin());}
#define TC_LOCAL_COMPILE
#ifdef TC_LOCAL_COMPILE
#include "hash_set"
#include "hash_map"
using namespace stdext;
#else
#include "ext/hash_set"
#include "ext/hash_map"
using namespace __gnu_cxx;
#endif
// END CUT HERE

vector <string> messages_;

struct CompanyMessages {
	
	vector<vector<int> > memo;
	vector<vector<int> > path;
	int calc(int rank_pos, int mask)
	{
		if(rank_pos >= messages_.size()) return 0;
		if(memo[rank_pos][mask] != -1) return memo[rank_pos][mask];

		int min_messges = std::numeric_limits<int>::max();
		for(int i=0; i<messages_.size(); ++i)
		{
			if((mask & (1<<i)) == 0)
			{
				int cost = 0;
				for(int j=0; j<messages_.size(); ++j) {
					if(mask & 1<<j) {
						cost += messages_[i][j] - '0';
					}
				}

				int num = calc(rank_pos+1, mask | 1<<i) + cost;
				if(num < min_messges)
				{
					path[rank_pos][mask] = i;
					min_messges = num;
				}
			}
		}

		memo[rank_pos][mask] = min_messges;
		return min_messges;
	}
	
	vector <int> getRank(vector <string> messages) {
	  messages_ = messages;

	  for(int i=0; i<16; ++i)
	  {
		  vector<int> memo_vec;
		  memo_vec.resize(1<<15, -1);
		  memo.push_back(memo_vec);

		  vector<int> path_vec;
		  path_vec.resize(1<<15, -1);
		  path.push_back(path_vec);
	  }

	  calc(0, 0);

	  vector<int> rank;
	  int mask = 0;
	  for(int i=0; i<messages.size(); ++i)
	  {
		  rank.push_back(path[i][mask]);
		  mask |= 1<<path[i][mask];
	  }

	  return rank;
  }
};






// BEGIN CUT HERE
namespace moj_harness {
  int isinf(double x) {return !_finite(x);}
  int isnan(double x) {return _isnan(x);}
};
namespace moj_harness {
	int run_test_case(int);
	void run_test( int casenum ) {
		if ( casenum != -1 ) {
			if ( run_test_case( casenum ) == -1 )
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			return;
		}
		
		int correct = 0, total = 0;
		for ( int i=0;; ++i ) {
			int x = run_test_case(i);
			if ( x == -1 ) {
				if ( i >= 100 ) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if ( total == 0 ) {
			cerr << "No test cases run." << endl;
		} else if ( correct < total ) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}
	
	template<typename T> ostream& operator<<( ostream &os, const vector<T> &v ) { os << "{"; for ( typename vector<T>::const_iterator vi=v.begin(); vi!=v.end(); ++vi ) { if ( vi != v.begin() ) os << ","; os << " " << *vi; } os << " }"; return os; }

	int verify_case( int casenum, const vector <int> &expected, const vector <int> &received ) { 
		cerr << "Example " << casenum << "... "; 
		if ( expected == received ) {
			cerr << "PASSED" << endl;
			return 1;
		} else {
			cerr << "FAILED" << endl;
			cerr << "    Expected: " << expected << endl; 
			cerr << "    Received: " << received << endl; 
			return 0;
		}
	}

	int run_test_case( int casenum ) {
		switch( casenum ) {
		case 0: {
			string messages[]         = {"000",  "000",  "000"};
			int expected[]            = {0, 1, 2 };

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}
		case 1: {
			string messages[]         = {"000",  "100",  "010"};
			int expected[]            = {2, 1, 0 };

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}
		case 2: {
			string messages[]         = {"012105","601745","830479","043086","349904","649810"};
			int expected[]            = {4, 2, 1, 5, 0, 3 };

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}

		// custom cases

      case 3: {
			string messages[]         = {"044454", "404434", "140444", "443044", "244404", "443440"};
			int expected[]            = {0, 2, 3, 4, 1, 5};

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}
/*      case 4: {
			string messages[]         = ;
			int expected[]            = ;

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}*/
/*      case 5: {
			string messages[]         = ;
			int expected[]            = ;

			return verify_case( casenum, vector <int>( expected, expected + ( sizeof expected / sizeof expected[0] ) ), CompanyMessages().getRank( vector <string>( messages, messages + ( sizeof messages / sizeof messages[0] ) ) ) );
		}*/
		default:
			return -1;
		}
	}
}

int main() {
  moj_harness::run_test(-1);
} 
// END CUT HERE
